\input basic
\parskip 12 pt
\parindent 0 pt
\magnify {1100}
\ctrline{\bf CS154 PROBLEM SET 5, SOLUTIONS}
4.1

(b) This can be derived from the recursive definition in problem 1.4.
$$S → ε \relv (S) \relv SS$$

(d) This can be derived from the definition of regular expression on
page 28.  Here $ε$ represents a symbol in a regular expression,
not the empty string.
$$S → \phi \relv ε \relv a \relv b \relv (S+S) \relv (SS) \relv (S↑{*})$$

4.5 (a)

$$E → T \relv T + E$$
$$T → F \relv F \ast T$$
$$F → \hbox{\bf\ id} \relv (E)$$

4.19

I will define an NFA that accepts the language of the CFG; therefore
the language is regular.

Let the states of the NFA be the symbols of the CFG, plus a unique
final state, $F$.  The start state of the automaton will be the start symbol
of the CFG.  For every production of the CFG of the form $A → wB$,
the automaton will have the transition $∂(A,w) = B$.  For every
transition of the CFG of the form $A → w$, the automaton will have
the transition $∂(A,w) = F$.

\vfill\eject

II.

We defined
$$X↓{∞} = \union↓{n=0}↑{∞}{f↑{(n)}(\phi)},$$
where $f↑{(0)}(X)$ is defined as $\phi$.

It was shown in class that $X↓{∞}$ is in fact a solution
of $X=f(X)$.  It remains to be shown that $X↓{∞}$ is a subset
of each solution of $X=f(X)$, and hence minimal.

Let $S$ be any solution of $X=f(X)$.  I will show that
${f↑{(n)}(\phi)}$ is a subset of $S$ for all $n ≥ 0$.  Hence, it will
follow that $X↓{∞}$ is a subset of $S$, completing the proof.

The proof will go by induction.  The basis case, $n=0$ is trivial,
since $f↑{(0)}(\phi) = \phi$, which is a subset of all sets.  Now suppose
that $f↑{(k)}(\phi)$ is a subset of $S$, for some $k ≥ 0$.  I think
that Professor Floyd showed in class that for any sets $U$ and $V$ such
that $U$ is a subset of $V$, $f(U)$ is a subset of $f(V)$.  Therefore,
$f(f↑{(k)}(\phi))$ is a subset of $f(S)$, which equals $S$; in other words,
$f↑{(k+1)}(\phi)$ is a subset of $S$.  This completes the induction.

II.

For $n>0$, $f↑{(n)}(\phi) = \{r↑{k}sr↑{k} \relv 0 ≤ k < n\}$, which can be proven
rigorously by an easy induction.  Therefore the minimal solution, which
is the union of all the sets above, is $\{r↑{k}sr↑{k} \relv k ≥ 0\}$.

\vfill\eject\end